The present invention relates to a method and apparatus for automatically designing a logic circuit, particularly a multiplier or a logic circuit including a multiplier, and to a multiplier.
Conventional multipliers for performing multiplication with digital information are often used not only as single, independent LSIs but also as elements to be mounted in such LSIs as DSP (digital signal processor). However, as the bit width is increased in multiplication and their applications are more diversified, multipliers of this type are required to have reduced circuit size and chip area as well as to operate at higher speed. To meet the requirements, circuit systems using various multiplication methods have been proposed.
For example, a multiplication method using the Booth's 2-bit recode system, which is one of the highest-speed multiplication methods, is disclosed in "Nikkei Electronics" (May 29, pp. 76-89 (1978)). The multiplication method uses the following algorithm in order to increase the speed of multiplication.
If an n-bit multiplicand X is to be multiplied by an m-bit multiplier factor Y, e.g., the multiplier factor Y is represented by two's complements as follows: ##EQU1## where ym=ys, q=m/2 if m is an even number or q=(m-1)/2 if m is an odd number, and y0=0 (y is a value given for convenience).
Hence, the product P of X and Y becomes ##EQU2##
Here, since the values of Y.sub.2i, Y.sub.2i+1, and Y.sub.2i+2 are 0 or 1, (y.sub.2i +y.sub.2i+1 -2y.sub.2i+2) becomes 0, .+-.1, or .+-.2, so that each of their partial products becomes a value obtained by multiplying 0, .+-.X, or .+-.2X by 2.sup.2i.
TABLE 1 ______________________________________ y.sub.2i+ 2 y.sub.2i+1 y.sub.2i (y.sub.2i + y.sub.2i+1 - 2y.sub.2i+2) ______________________________________ 0 0 0 0 0 0 1 +1 0 1 0 +1 0 1 1 +2 1 0 0 -2 1 0 1 -1 1 1 0 -1 1 1 1 0 ______________________________________
Here, a circuit for generating the partial products can be composed of a shifter primarily for shifting the multiplicand .+-.X by one bit till it is doubled and a shifter for shifting a mantissa (0, .+-.X or .+-.2X) by two bits till it is raised to the power of 2.sup.2i (weighing).
As for the number of logic stages in a circuit for calculating the total sum of the partial products, since the number of the partial products becomes q=m/2 (m is an even number) or q=(m-1)/2 (m is an odd number), it becomes approximately log.sub.2 m-1 (m is an even number) or log.sub.2 (m-1)-1 (m is an odd number) when a 2-input adder is connected so as to form a binary tree.
As an example of high-speed multipliers not using the Booth's 2-bit recode system, Japanese Patent Publication no. 03-017737 discloses a multiplier using redundant binary code.
With the multiplier mentioned above, when the multiplier factor is composed of 24 bits, the number of its partial products becomes 12 and the number of its logic stages becomes 4.
On the other hand, the increase in multiplication speed and the decrease in circuit size have been pursued not only by improving the performance of such a multiplication algorithm as mentioned above, but also by optimizing the circuit on the level of logic elements.
In recent years, multipliers and logic circuits containing multipliers are mostly designed by using automatic designing systems. Such a system is intended to eliminate a redundant portion of the circuit or to perform other operations by replacing a part of the circuit with an equivalent circuit having a smaller number of logic elements and logic stages in the case of, e.g., expanding circuit information on the level of logic elements to circuit information on the level of mounted elements, which are actually mounted in a chip.
If functional description information, which represents a function requested on the circuit in a hardware description language or the like, is inputted to such an automatic designing system, the system converts it to functional circuit information in an internal representation form, which represents a circuit composed of virtual functional elements whose functions are primarily and solely defined. Then, the resulting functional circuit information is further converted to logic circuit information which represents a circuit composed of real logic circuits, followed by the generation of mounted circuit information which represents a circuit to which real elements, mounted by specified technology, are allotted.
With the conventional automatic designing systems, however, the optimization of the circuit on the level of logic elements is localized, for the replacement by an equivalent circuit having a smaller number of logic elements and logic stages is limited to portions of the circuit that coincide with specific patterns which were preliminarily set. If such optimization is performed in the case where the multiplier factor or multiplicand is a constant, a circuit having the minimum number of logic elements and the like cannot necessarily be obtained. In particular, when a two-input adder for adding partial products is connected so as to form a binary tree, the balance between two branches is normally destroyed if the portion associated with the add circuit for the partial products, in which the values of all the bits are 0, is omitted. Therefore, it is difficult to minimize the number of logic elements and the number of logic stages by partially replacing the circuit.